﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CodeTop.CodeTop
{
    public class Solution139
    {
        public bool WordBreak(string s, IList<string> wordDict)
        {


            int len = s.Length;
            bool[] dp = new bool[len+1];//多一维，没有字母组成的true
            dp[0] = true;

            for (int i = 1; i <= len; i++)//以第i个字母结尾的子串能否组成
            {


                for (int j = 0; j < wordDict.Count; j++)
                {

                    string curStr = wordDict[j];
                    int curStrLen = curStr.Length;

                    if (i  >= curStrLen)
                    {
                       
                        string sChild = s.Substring(i  - curStrLen, curStrLen);
                        Console.WriteLine(sChild);
                        //现在的子串能否由字典里面的组成
                        bool isBreak = sChild.Equals(curStr);
                        dp[i] = dp[i] || (dp[i  - curStrLen] && isBreak);
                    }

                }

            }


            return dp[len ];



        }
    }

    class Program139
    {




        static void Main139()
        {

            string s = "leetcode"; IList<string> wordDict = ["leet", "code"];


            Solution139 sol = new Solution139();
            Console.WriteLine(sol.WordBreak(s, wordDict)); 


        }
    }
}
